`
https://leetcode.cn/problems/maximum-total-damage-with-spell-casting/
`

/**
 * @param {number[]} power
 * @return {number}
 */
var maximumTotalDamage = function (power) {
  // 打家劫舍问题，power[i] 太大，不能直接在伤害值上进行动态规划
  // 统计每个伤害值出现的次数
  const count = new Map()
  for (const p of power) {
    count.set(p, (count.get(p) || 0) + 1)
  }
  // 伤害值以升序排序
  const keys = Array.from(count.keys()).sort(((a, b) => a - b))
  // 升序放到一个数组里，由于伤害值从 1 开始，先在 0 占个位
  const vec = [[-1e9, 0]]
  for (const k of keys) {
    vec.push([k, count.get(k)])
  }
  // dp[i] 表示考虑前 i 种不同伤害值时，并且 必须选择 第 i 种时，能获得的最大总伤害
  /**
   * 对于当前考虑的伤害值 p_i，我们有两种选择：
   * 不使用伤害为 p_i 的所有咒语。那么最大伤害等于考虑上一个伤害值 p_{i-1} 时的最大伤害。
   * 使用伤害为 p_i 的所有咒语。这会获得 p_i * count(p_i) 的伤害。根据规则，我们就不能使用伤害值在 [p_i-2, p_i+2] 区间内的其他咒语。由于我们是按伤害值从小到大处理的，我们只需要确保之前选择的咒语伤害值 p_j 满足 p_j < p_i - 2。因此，我们需要找到满足这个条件的、能产生最大伤害的那个之前的状态。
   */
  const n = vec.length
  const dp = new Array(n).fill(0)
  let res = 0, maxVal = 0, j = 1
  for (let i = 1; i < n; i++) {
    while (j < i && vec[j][0] < vec[i][0] - 2) {
      // 维护 dp[1...j] 中所有满足 vec[j][0] < vec[i][0] - 2 的最大值
      maxVal = Math.max(maxVal, dp[j])
      j++
    }
    // 选择 i 时的最大值即为当前伤害值的收益加上之前满足条件的最大值
    dp[i] = maxVal + vec[i][0] * vec[i][1]
    // 答案不一定是选择最后一个，需要维护一个 dp 里的最大值
    res = Math.max(res, dp[i])
  }
  return res
};